import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Num15 {
    /**
     * 排序加双指针
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3) return res;

        Arrays.sort(nums);

        for (int i = 0; i < nums.length;) {
            int left = i + 1;
            int right = nums.length - 1;

            while(left < right){
                if (nums[left] + nums[right] == -nums[i]){
                    List<Integer> list = Arrays.asList(nums[i], nums[left], nums[right]);
                    res.add(list);

                    while(left < nums.length-1 && nums[left] == nums[left+1]) left++;
                    left++;
                    while(right > 0 && nums[right] == nums[right-1]) right--;
                    right--;
                    continue;
                }

                if (nums[left] + nums[right] < -nums[i]){
                    while(left < nums.length-1 && nums[left] == nums[left+1]) left++;
                    left++;
                } else {
                    while(right > 0 && nums[right] == nums[right-1]) right--;
                    right--;
                }

            }

            while(i < nums.length-1 && nums[i] == nums[i+1]) i++;
            i++;
        }

        return res;
    }

    public static void main(String[] args) {
        Num15 num15 = new Num15();
        System.out.println(num15.threeSum(new int[]{0,0,0}));
    }
}
